package 高级班;


//给定字符串str1和str2，求str1的子串中含有str2所有字符的最小子串长度
public class dsf {
    public static int minLength(String str1, String str2) {
        if (str1 == null || str2 == null || str1.length() < str2.length()) {
            return 0;
        }
        char[] chas1 = str1.toCharArray();
        char[] chas2 = str2.toCharArray();
        int[] map = new int[256];
        for (int i = 0; i != chas2.length; i++) {
            map[chas2[i]]++;
        }
        int left = 0;
        int right = 0;
        int match = chas2.length;
        int minLen = Integer.MAX_VALUE;
        while (right != chas1.length) {
            map[chas1[right]]--;
            if (map[chas1[right]] >= 0) {
                match--;
            }
            if (match == 0) {
                while (map[chas1[left]] < 0) {
                    map[chas1[left++]]++;
                }
                minLen = Math.min(minLen, right - left + 1);
                match++;
                map[chas1[left++]]++;
            }
            right++;
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }

    public static int minLength_ytc(String s1,String s2){
        int[] map=new int[26];
        for (int i=0;i<s2.length();i++)
            map[s2.charAt(i)-'a']++;
        int diff=s2.length();
        int left=0;
        int right=0;
        int minLen=Integer.MAX_VALUE;
        while (right<s2.length()){
            map[s2.charAt(right)-'a']--;
            if (map[s2.charAt(right)-'a']>=0)
                diff--;
            if (diff==0){
                while (map[s1.charAt(left)-'a']<0){
                    map[s1.charAt(left)-'a']++;
                    left++;
                }
                minLen=Math.min(minLen,right-left+1);
                diff++;
                map[s1.charAt(left++)-'a']++;
            }
            right++;
        }
        return minLen;
    }

    public static void main(String[] args) {
        String str1 = "adabbca";
        String str2 = "acb";
        System.out.println(minLength(str1, str2));
        System.out.println(minLength_ytc(str1,str2));

    }
}
